這是我很喜歡的主題，但今天依舊不舒服而且我隊友不安ㄌ只好先斷尾求生

InnoDB

InnoDB 是資料庫引擎，
因為支援 Transaction，目前是 MySQL 的預設引擎。（早期是 MyISAM）
[[這裏補張 dbms的結構圖好ㄌ]]
以我目前的認知，不同存儲引擎的差異主要在於「indexing」

Indexing

有上過資料結構都知道，一堆資料如果要查詢效率高，最好是排序過。
這就是為什麼需要做索引了，
其實就只是把會常常查詢的那個 column 拿出來，並以此 column 數值來排序所有的 records。

clustered index

• primary key
• 資料實際上就是依照這種 index 排序

non-clustered index（secondary index）

• 通常人家說做 indexing 會比較快，是指這種 index
• 如果表中有常會需要拿來查詢比較的 column（attribute），拿出來做 non-clustered index
• 做出另一棵依照此 column 排序的樹，查詢出的數值為 clustered index，再去存放所有資料的那棵樹以 clustered index 取需要的資料
• 其實我覺得稱 secondary index 更容易懂，用二級索引查出主索引，再取得資料

如果再講底層一些，densed indexing 與 multilevel-indexing

densed indexing

今天存資料到硬碟上，根據 table schema 每條資料會佔用一定大小，
這樣查詢資料會很費時。

因此我們需要一個表紀錄 index + 屬於這個 index 的資料在哪，
而這個 index 表每條資料的大小應該會比原來的 table 小，
這樣載入到記憶體中時，同樣大小可以知道更多「資料在哪」的資訊。

所以如果今天 column 很少，或許就沒有額外做 densed indexing 的必要呢

multilevel-indexing

如果資料變多，densed index 一直增加下去，O(n) 的 n 越來越大也不是辦法。
那就多增加幾層吧，類似 virtual memory 的 multi-level page table 的概念。

clustered/non-clustered index vs multilevel-indexing

我覺得主要差在作用層次與目的。

• clustered / non-clustered 是高層次存資料時「開發者」可以做的選擇。
• multilevel-indexing 是底層存儲到硬碟上，為避免 index 增長太大，以減少 IO 次數的方法。
  兩者都是由 sparsed index 查出真正的 densed index，再去最上層的表取值。

B tree B+ tree

而有某種程度的「排序」+「動態刪減」的資料結構，就會想到 binary tree，
B tree 和 B+ tree 可以說是 binary tree 的延伸變種。

什麼時候做 indexing？

索引說白了就是以空間換搜尋時間提升，所以不能每個 column 都做索引。

• primary key (定義 table 時應該就要寫好）
• foreign key
• 常常查詢的欄位（ORDER BY / WHERE / GROUP BY）
  建立索引表除了需要空間，每次新增刪除等操作，都要額外花時間去索引表作更動（想像要去樹上新增刪除節點）